package day4;

public class ch2 {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    //142
    public ListNode detectCycle(ListNode head) {

        if(head==null || head.next==null || head.next.next==null ) return null;


        ListNode a = head;
        ListNode b = head;

        while (b.next!=null&&b.next.next!=null){
            a = a.next;
            b = b.next.next;
            if(a==b){
                break;
            }
        }
        if(a!=b){
            return null;
        }
        ListNode node = a;
        while (node!=head){
            node = node.next;
            head = head.next;
        }
        return node;
    }

    //21
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null) return list2;
        if(list2==null) return list1;

        ListNode head,p,q;
        if(list1.val<list2.val){
             head = list1;
             p = list1.next;
             q = list2;
        }else {
             head = list2;
             p = list2.next;
             q = list1;
        }
        head.next = null;
        ListNode last = head;

        while (p!=null && q!=null){
            if(p.val<q.val){
                ListNode next = p.next;
                p.next = null;
                last.next = p;
                last = p;
                p = next;
            }else {
                ListNode next = q.next;
                q.next = null;
                last.next = q;
                last = q;
                q = next;
            }
        }

        if(p!=null){
            last.next = p;
        }
        if(q!=null){
            last.next = q;
        }

        return head;

    }


    //2
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode p = l1;
        ListNode q = l2;

        ListNode node = new ListNode(0);
        ListNode index = node;
        int num = 0;
        while (p!=null || q!=null ){
            int a = 0;
            int b = 0;
            if(p!=null) a = p.val;
            if(q!=null) b = q.val;

            int v = a+b+num;
            num = v>=10?1:0;

            index.next = new ListNode(v%10);
            index = index.next;

            if(p!=null) p = p.next;
            if(q!=null) q = q.next;
        }

        if(num>0){
            index.next = new ListNode(num);
        }

        return node.next;
    }

    public ListNode fun(ListNode head){

        ListNode node = head.next;
        head.next = null;

        while (node!=null){
            ListNode next = node.next;
            node.next = head;
            head = node;
            node = next;
        }

        return head;
    }


    //19
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode p = head;
        for (int i = 0; i < n; i++) {
            p = p.next;
        }
        if(p==null){
            return head.next;
        }


        ListNode q =head;
        while (p.next!=null){
            q = q.next;
            p = p.next;
        }
        if(q==head){
            return head.next;
        }
        q.next = q.next.next;

        return head;


    }

    //24
    public ListNode swapPairs(ListNode head) {
        if(head==null || head.next==null) return head;

        ListNode n = head.next;
        head.next=n.next;
        n.next = head;
        ListNode node = head;
        head = n;

        while (node.next!=null&&node.next.next!=null){
             ListNode p = node.next;
             ListNode q = node.next.next;

             ListNode next = q.next;
             node.next=q;
             q.next = p;
             p.next = next;
             node = p;

        }

        return head;

    }





}
